<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>每日一DP(2) CF191A (线性DP) | FZSF</title><meta name="keywords" content="动态规划"><meta name="author" content="FZSF"><meta name="copyright" content="FZSF"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="题目题目描述 The ancient Berlanders believed that the longer the name, the more important its bearer is. Thus, Berland kings were famous for their long names. But long names are somewhat inconvenient, so th">
<meta property="og:type" content="article">
<meta property="og:title" content="每日一DP(2) CF191A (线性DP)">
<meta property="og:url" content="https://fanzsfu.gitee.io/2021/11/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-2-CF191A-%E7%BA%BF%E6%80%A7DP/index.html">
<meta property="og:site_name" content="FZSF">
<meta property="og:description" content="题目题目描述 The ancient Berlanders believed that the longer the name, the more important its bearer is. Thus, Berland kings were famous for their long names. But long names are somewhat inconvenient, so th">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://pic.imgdb.cn/item/618f6bec2ab3f51d914eee77.jpg">
<meta property="article:published_time" content="2021-11-13T07:38:59.000Z">
<meta property="article:modified_time" content="2021-11-13T08:01:49.630Z">
<meta property="article:author" content="FZSF">
<meta property="article:tag" content="动态规划">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://pic.imgdb.cn/item/618f6bec2ab3f51d914eee77.jpg"><link rel="shortcut icon" href="/img/tou.png"><link rel="canonical" href="https://fanzsfu.gitee.io/2021/11/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-2-CF191A-%E7%BA%BF%E6%80%A7DP/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '每日一DP(2) CF191A (线性DP)',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2021-11-13 16:01:49'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if (GLOBAL_CONFIG_SITE.isHome && /iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><meta name="generator" content="Hexo 5.4.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://pic.imgdb.cn/item/6118dff15132923bf87690a5.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">20</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">5</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://pic.imgdb.cn/item/618f6bec2ab3f51d914eee77.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">FZSF</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">每日一DP(2) CF191A (线性DP)</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-11-13T07:38:59.000Z" title="发表于 2021-11-13 15:38:59">2021-11-13</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-11-13T08:01:49.630Z" title="更新于 2021-11-13 16:01:49">2021-11-13</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%AF%8F%E6%97%A5%E4%B8%80%E9%A2%98/">每日一题</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">983</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>4分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="每日一DP(2) CF191A (线性DP)"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h2><p><strong>题目描述</strong></p>
<p>The ancient Berlanders believed that the longer the name, the more important its bearer is. Thus, Berland kings were famous for their long names. But long names are somewhat inconvenient, so the Berlanders started to abbreviate the names of their kings. They called every king by the first letters of its name. Thus, the king, whose name was Victorious Vasily Pupkin, was always called by the berlanders VVP.</p>
<p>In Berland over its long history many dynasties of kings replaced each other, but they were all united by common traditions. Thus, according to one Berland traditions, to maintain stability in the country, the first name of the heir should be the same as the last name his predecessor (hence, the first letter of the abbreviated name of the heir coincides with the last letter of the abbreviated name of the predecessor). Berlanders appreciate stability, so this tradition has never been broken. Also Berlanders like perfection, so another tradition requires that the first name of the first king in the dynasty coincides with the last name of the last king in this dynasty (hence, the first letter of the abbreviated name of the first king coincides with the last letter of the abbreviated name of the last king). This tradition, of course, has also been always observed.</p>
<p>The name of a dynasty is formed by very simple rules: we take all the short names of the kings in the order in which they ruled, and write them in one line. Thus, a dynasty of kings “ab” and “ba” is called “abba”, and the dynasty, which had only the king “abca”, is called “abca”.</p>
<p>Vasya, a historian, has recently found a list of abbreviated names of all Berland kings and their relatives. Help Vasya to find the maximally long name of the dynasty that could have existed in Berland.</p>
<p>Note that in his list all the names are ordered by the time, that is, if name $A$ is earlier in the list than $B$, then if $A$ and $B$ were kings, then king $A$ ruled before king $B$.</p>
<p><strong>输入描述</strong></p>
<p>The first line contains integer $n~(1 \leq n \leq 5·10^5)$ — the number of names in Vasya’s list. Next $n$ lines contain $n$ abbreviated names, one per line. An abbreviated name is a non-empty sequence of lowercase Latin letters. Its length does not exceed $10$ characters.</p>
<p><strong>输出描述</strong></p>
<p>Print a single number — length of the sought dynasty’s name in letters.</p>
<p>If Vasya’s list is wrong and no dynasty can be found there, print a single number $0$.</p>
<p><strong>Examples</strong></p>
<p><strong>input</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">3</span><br><span class="line">abc</span><br><span class="line">ca</span><br><span class="line">cba</span><br></pre></td></tr></table></figure>
<p><strong>output</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">6</span><br></pre></td></tr></table></figure>
<p><strong>input</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">4</span><br><span class="line">vvp</span><br><span class="line">vvp</span><br><span class="line">dam</span><br><span class="line">vvp</span><br></pre></td></tr></table></figure>
<p><strong>output</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">0</span><br></pre></td></tr></table></figure>
<p><strong>input</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">3</span><br><span class="line">ab</span><br><span class="line">c</span><br><span class="line">def</span><br></pre></td></tr></table></figure>
<p><strong>output</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">1</span><br></pre></td></tr></table></figure>
<h4 id="大体题意"><a href="#大体题意" class="headerlink" title="大体题意"></a>大体题意</h4><p>题面一堆废话，简化一下就是：</p>
<p>给你$n$个长度不超过$10$的只有小写字母的字符串。</p>
<p>求把他们连起来之后最长的长度，只有前一个字符串的最后一个字母和</p>
<p>后一个字符串的第一个字母相同时才可以连接，并且最后得到的字符串第一个字母必须和最后一个字母一样（如果连了好几个，只看第一个和最后一个）</p>
<p>并且连接的时候必须按输入顺序连接，如$1$可以连$2$……$n$，但$2$不能连$1$。</p>
<h4 id="思路"><a href="#思路" class="headerlink" title="思路"></a>思路</h4><p>当我们理解了题意之后，很快就可以分析出能否连接只和前一个字符串的最后一个字母以及后一个字符串的第一个字母有关。</p>
<p>所以我们可以用$dp[i] [j]$代表以$i$开头，以$j$结尾的字符串的最长长度。</p>
<p>很显然当目前的字符串以$s$开头，以$e$结尾，并且长度为$len$时的DP方程为：</p>
<script type="math/tex; mode=display">
dp[i][e]=max(dp[i][e],dp[i][s]+len)</script><p>得到方程之后我们需要考虑转移条件。</p>
<p>很显然，当没有$dp[i] [s]$时，就无法完成转移，所以在进行转移时需要判断一下。</p>
<p>其次，需要在当前字符串转移完成之后再用$len$更新$dp[s] [e]$，否则会将自身累加两次。</p>
<h2 id="AC代码"><a href="#AC代码" class="headerlink" title="AC代码"></a>AC代码</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">double</span> db;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">5e5</span>+<span class="number">10</span>;</span><br><span class="line">string a[N];</span><br><span class="line"><span class="keyword">int</span> dp[<span class="number">30</span>][<span class="number">30</span>];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++) cin&gt;&gt;a[i];</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">int</span> s=a[j][<span class="number">0</span>]-<span class="string">&#x27;a&#x27;</span>,e=a[j][(<span class="keyword">int</span>)a[j].<span class="built_in">size</span>()<span class="number">-1</span>]-<span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">26</span>;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span>(dp[i][s]) dp[i][e]=<span class="built_in">max</span>(dp[i][e],dp[i][s]+(<span class="keyword">int</span>)a[j].<span class="built_in">size</span>());</span><br><span class="line">		&#125;</span><br><span class="line">		dp[s][e]=<span class="built_in">max</span>(dp[s][e],(<span class="keyword">int</span>)a[j].<span class="built_in">size</span>());</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">26</span>;i++) </span><br><span class="line">	&#123;</span><br><span class="line">		ans=<span class="built_in">max</span>(dp[i][i],ans);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,ans);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>提交记录：<a target="_blank" rel="noopener" href="https://codeforces.com/problemset/submission/191/135230950">Submission #135230950 - Codeforces</a></p>
<p>原题链接：<a target="_blank" rel="noopener" href="https://codeforces.com/problemset/problem/191/A">Problem - 191A - Codeforces</a></p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">FZSF</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://fanzsfu.gitee.io/2021/11/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-2-CF191A-%E7%BA%BF%E6%80%A7DP/">https://fanzsfu.gitee.io/2021/11/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-2-CF191A-%E7%BA%BF%E6%80%A7DP/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://fanzsfu.gitee.io" target="_blank">FZSF</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></div><div class="post_share"><div class="social-share" data-image="https://pic.imgdb.cn/item/618f6bec2ab3f51d914eee77.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2021/11/14/2021ICPC%E6%B5%8E%E5%8D%97%E7%AB%99%E6%B8%B8%E8%AE%B0/"><img class="prev-cover" src="https://pic.imgdb.cn/item/6190e7102ab3f51d91c86365.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">2021ICPC济南站游记</div></div></a></div><div class="next-post pull-right"><a href="/2021/11/12/%E6%AF%8F%E6%97%A5%E4%B8%80DP-1-CF946D-%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85-%E9%A2%84%E5%A4%84%E7%90%86/"><img class="next-cover" src="https://pic.imgdb.cn/item/60a9dd7f35c5199ba7dded6b.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">每日一DP(1) CF946D (分组背包+预处理)</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span> 相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2021/11/12/每日一DP-1-CF946D-分组背包-预处理/" title="每日一DP(1) CF946D (分组背包+预处理)"><img class="cover" src="https://pic.imgdb.cn/item/60a9dd7f35c5199ba7dded6b.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-11-12</div><div class="title">每日一DP(1) CF946D (分组背包+预处理)</div></div></a></div><div><a href="/2021/11/15/每日一DP-3-CF455A-线性DP/" title="每日一DP(3) CF455A (线性DP)"><img class="cover" src="https://pic.imgdb.cn/item/6191f6022ab3f51d9115e383.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-11-15</div><div class="title">每日一DP(3) CF455A (线性DP)</div></div></a></div><div><a href="/2022/01/13/每日一DP-5-CF1625C-线性DP/" title="每日一DP(5) CF1625C (线性DP)"><img class="cover" src="https://pic.imgdb.cn/item/61dffe022ab3f51d91788e88.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-01-13</div><div class="title">每日一DP(5) CF1625C (线性DP)</div></div></a></div><div><a href="/2022/03/21/每日一DP-6-Leetcode-2172-状压DP/" title="每日一DP(6) Leetcode 2172(状压DP)"><img class="cover" src="https://pic.imgdb.cn/item/6237ef7527f86abb2af1c508.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-03-21</div><div class="title">每日一DP(6) Leetcode 2172(状压DP)</div></div></a></div><div><a href="/2021/08/23/算法学习笔记-2——树型DP/" title="算法学习笔记(2)——树型DP"><img class="cover" src="https://pic.imgdb.cn/item/6123b76844eaada739b8cba7.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-08-23</div><div class="title">算法学习笔记(2)——树型DP</div></div></a></div><div><a href="/2021/11/16/每日一DP-4-CF1061C-数学-线性DP-预处理/" title="每日一DP(4) CF1061C(数学+线性DP+预处理)"><img class="cover" src="https://pic.imgdb.cn/item/6193c6152ab3f51d91b888ad.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-11-16</div><div class="title">每日一DP(4) CF1061C(数学+线性DP+预处理)</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://pic.imgdb.cn/item/6118dff15132923bf87690a5.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">FZSF</div><div class="author-info__description">记录与成长</div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">20</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">5</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/Elbow-Leaf"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">This is my Blog</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE"><span class="toc-number">1.</span> <span class="toc-text">题目</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A4%A7%E4%BD%93%E9%A2%98%E6%84%8F"><span class="toc-number">1.0.1.</span> <span class="toc-text">大体题意</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF"><span class="toc-number">1.0.2.</span> <span class="toc-text">思路</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#AC%E4%BB%A3%E7%A0%81"><span class="toc-number">2.</span> <span class="toc-text">AC代码</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2022/06/04/2022%E5%B9%B4%E5%B1%B1%E4%B8%9C%E7%9C%81ICPC%E7%9C%81%E8%B5%9B%E6%B8%B8%E8%AE%B0/" title="2022年山东省ICPC省赛游记"><img src="https://pic.imgdb.cn/item/629b123b09475431292426f7.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022年山东省ICPC省赛游记"/></a><div class="content"><a class="title" href="/2022/06/04/2022%E5%B9%B4%E5%B1%B1%E4%B8%9C%E7%9C%81ICPC%E7%9C%81%E8%B5%9B%E6%B8%B8%E8%AE%B0/" title="2022年山东省ICPC省赛游记">2022年山东省ICPC省赛游记</a><time datetime="2022-06-04T07:59:36.000Z" title="发表于 2022-06-04 15:59:36">2022-06-04</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/04/11/%E5%B1%B1%E4%B8%9C%E5%A4%9A%E6%A0%A1%E9%9B%86%E8%AE%AD1%E6%80%BB%E7%BB%93%EF%BC%88%E6%B5%81%E6%B0%B4%E8%B4%A6%EF%BC%89%E9%99%84%E4%B8%8D%E5%AE%8C%E5%85%A8%E9%A2%98%E8%A7%A3/" title="山东多校集训1总结（流水账）附不完全题解"><img src="https://pic.imgdb.cn/item/6253b949239250f7c54a1415.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="山东多校集训1总结（流水账）附不完全题解"/></a><div class="content"><a class="title" href="/2022/04/11/%E5%B1%B1%E4%B8%9C%E5%A4%9A%E6%A0%A1%E9%9B%86%E8%AE%AD1%E6%80%BB%E7%BB%93%EF%BC%88%E6%B5%81%E6%B0%B4%E8%B4%A6%EF%BC%89%E9%99%84%E4%B8%8D%E5%AE%8C%E5%85%A8%E9%A2%98%E8%A7%A3/" title="山东多校集训1总结（流水账）附不完全题解">山东多校集训1总结（流水账）附不完全题解</a><time datetime="2022-04-11T04:18:00.000Z" title="发表于 2022-04-11 12:18:00">2022-04-11</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/03/21/%E6%AF%8F%E6%97%A5%E4%B8%80DP-6-Leetcode-2172-%E7%8A%B6%E5%8E%8BDP/" title="每日一DP(6) Leetcode 2172(状压DP)"><img src="https://pic.imgdb.cn/item/6237ef7527f86abb2af1c508.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="每日一DP(6) Leetcode 2172(状压DP)"/></a><div class="content"><a class="title" href="/2022/03/21/%E6%AF%8F%E6%97%A5%E4%B8%80DP-6-Leetcode-2172-%E7%8A%B6%E5%8E%8BDP/" title="每日一DP(6) Leetcode 2172(状压DP)">每日一DP(6) Leetcode 2172(状压DP)</a><time datetime="2022-03-21T02:40:26.000Z" title="发表于 2022-03-21 10:40:26">2022-03-21</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/03/18/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-8-%E2%80%94%E2%80%94%E8%83%8C%E5%8C%85DP/" title="算法学习笔记(8)——背包DP"><img src="https://pic.imgdb.cn/item/623403185baa1a80abe33090.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="算法学习笔记(8)——背包DP"/></a><div class="content"><a class="title" href="/2022/03/18/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-8-%E2%80%94%E2%80%94%E8%83%8C%E5%8C%85DP/" title="算法学习笔记(8)——背包DP">算法学习笔记(8)——背包DP</a><time datetime="2022-03-18T00:58:52.000Z" title="发表于 2022-03-18 08:58:52">2022-03-18</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/01/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-5-CF1625C-%E7%BA%BF%E6%80%A7DP/" title="每日一DP(5) CF1625C (线性DP)"><img src="https://pic.imgdb.cn/item/61dffe022ab3f51d91788e88.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="每日一DP(5) CF1625C (线性DP)"/></a><div class="content"><a class="title" href="/2022/01/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-5-CF1625C-%E7%BA%BF%E6%80%A7DP/" title="每日一DP(5) CF1625C (线性DP)">每日一DP(5) CF1625C (线性DP)</a><time datetime="2022-01-13T10:03:53.000Z" title="发表于 2022-01-13 18:03:53">2022-01-13</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2021 - 2022 By FZSF</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
  window.MathJax = {
    tex: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]],
      tags: 'ams'
    },
    chtml: {
      scale: 1.2
    },
    options: {
      renderActions: {
        findScript: [10, doc => {
          for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
            const display = !!node.type.match(/; *mode=display/)
            const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
            const text = document.createTextNode('')
            node.parentNode.replaceChild(text, node)
            math.start = {node: text, delim: '', n: 0}
            math.end = {node: text, delim: '', n: 0}
            doc.math.push(math)
          }
        }, ''],
        insertScript: [200, () => {
          document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
            const target = node.parentNode
            if (target.nodeName.toLowerCase() === 'li') {
              target.parentNode.classList.add('has-jax')
            } else {
              target.classList.add('has-jax')
            }
          });
        }, '', false]
      }
    }
  }
  
  const script = document.createElement('script')
  script.src = 'https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'
  script.id = 'MathJax-script'
  script.async = true
  document.head.appendChild(script)
} else {
  MathJax.startup.document.state(0)
  MathJax.texReset()
  MathJax.typeset()
}</script></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>